The present invention relates generally to content addressable memories (CAMs), and more particularly to methods for updating search tables in CAMs.
One type of device that has found wide application in the field of networking is the content addressable memory (CAM). Many networking applications can require a match function. To perform a typical match function, a CAM can include a number of entries that store data values. The data values stored in a CAM may be conceptualized as a xe2x80x9ctable.xe2x80x9d Each data value can include match criteria that can be considered a xe2x80x9crule.xe2x80x9d
An input value (a query or comparand) can be applied to the CAM and essentially simultaneously with the table of rules. If a rule matches the query a match indication can be generated. Typically, a CAM can include a priority encoder to select from among multiple match indications. Conventionally, a priority encoder establishes priority according to the data value position within a CAM. Data value position is typically a CAM address.
In the field of networking, CAMs can be used to process network packets. Network packets can include a header with a number of data fields. Selected data fields can be extracted from a header and applied to a CAM. The CAM can compare an extracted data field with its table data values essentially simultaneously. If a header field matches a data value within the CAM, a match indication can be generated. A CAM match indication can generate associated data that can be used to process a packet.
As but a few of the many applications, a CAM can be used to in route forwarding. According to match indications provided by the CAM, a packet can be transmitted from one network node to the next. A CAM may also be used in packet filtering. Match indications (or lack thereof) can be used to prevent a packet from being allowed into, or transmitted from, a network. Still further, a CAM can be utilized to establish flow classification. Match indications can be used to direct packets along particular predetermined data flow routes.
By providing rapid, parallel matching of data values to an applied input value (a comparand), a CAM can provide a rapid matching function.
CAMs can include binary CAMs and ternary CAMs. A conventional binary CAM can compare data values of fixed size to comparand values of the same size. While useful for straightforward match functions, conventional binary CAMs cannot provide more complex match functions. In particular, it is often desirable to provide a match function between a comparand value and portions of a data values within a table. These and other more complex matching functions can be accomplished with a ternary (or xe2x80x9ctertiaryxe2x80x9d) CAM.
A ternary CAM can store data values that can be xe2x80x9cmasked.xe2x80x9d In a conventional ternary CAM, data values can be masked on a bit-by-bit basis. Thus, a valid ternary CAM entry can include masked and unmasked bits. Conventionally, an unmasked bit can be a xe2x80x9c1xe2x80x9d or xe2x80x9c0xe2x80x9d that is compared to the 1 or 0 of a comparand bit to generate a bit match or no match. A masked bit, often identified as xe2x80x9cX,xe2x80x9d will provide a bit match regardless of its corresponding comparand bit value.
By masking a trailing portion of a data value, a conventional ternary CAM can provide a longest prefix match function. By masking various non-contiguous portions of a data value, a ternary CAM can provide a masked prefix match function. Longest and masked prefix matching can be important operations in a network hardware device.
A conventional ternary CAM, as noted above, can include a priority encoder that establishes priority according to position within a CAM.
While CAM priority encoders can allow for rapid match functions, such arrangements can have drawbacks. If data values stored in a CAM table remained static, matching functions could be undertaken without interruption and at high speed. Unfortunately, in most networking applications CAM data values can be continuously updated. As just a few examples, the data values in a route forwarding CAM may frequently change due to shortest path calculations of a routing protocol. Further, routers and/or switches in a network may be added or deleted, requiring a table update operation. Conventionally, if a new data value is added to a CAM, the new value must be placed within the CAM between those entries having a higher priority and those entries having a lower priority.
An example of a conventional CAM match and update operation will now be described. Referring now to FIGS. 14A to 14B, a portion of a CAM table is set forth in a sequence of diagrams.
FIG. 14A illustrates a CAM table prior to an update operation. The CAM table includes four locations, 0 to 3, that store data values A to D. In the arrangement of FIG. 14A it is assumed that priority is established according to lowest location. Thus, if an applied comparand value indicates a match with data value A and data value D, the match with data value A will have priority.
FIGS. 14B and 14C shown an update operation to the CAM table. The update operation includes the addition of a data value xe2x80x9cYxe2x80x9d having a priority that is less than data values A and B, but greater than data values C and D. As shown by FIG. 14B, in order to ensure data value Y will have the desired priority, data values C and D must be moved to locations of lower priority. Thus, data values C and D are moved to locations 3 and 4, respectively. As shown by FIG. 14C, by moving data values of lesser priority, the new data value Y can be written into location 2.
CAM densities continue to increase. Currently, CAMs can include as many as 512 k entries. As densities increase CAMs may include millions of entries. Thus, conventional approaches to updating such large tables can be impractical. First, update operations for very large tables can consume processing resources. For example, if a CAM is utilized in conjunction with a central processing unit (CPU), the numerous copying operations required for some update operations can tie up the system CPU slowing down input/output operations in the system. Such slowdowns can be exacerbated because CAM data cannot typically be cached.
Conventional CAM update operations can also impact network device performance. For example, a router and/or network switch that includes a CAM can receive packets on a continuous basis. However, within a conventional CAM, the data and/or control paths that are used to perform a match function are not separate from those used to perform an update operation. Consequently, update operations of a CAM can prevent match functions from taking place, slowing down a network device""s performance.
Nonconventional CAMs can include an intrinsic xe2x80x9cblock move.xe2x80x9d A block move can allow a CAM to move data values without taxing CPU resources. Unfortunately, including block move capabilities in a CAM can add to the complexity and/or cost of a CAM. Further, while a block move can free CPU resources, update operations may still interfere with match functions.
It would be desirable to provide some way of managing data values within CAM that does not include the drawbacks of conventional arrangements. Such a method could preferably be used in conjunction with conventional ternary CAMs.
According to one embodiment, a CAM can receive input values as queries. Various entries within the CAM can be conceptualized as including a matching rule and a priority. A method for updating entries in a CAM can include determining if a new entry overlaps any existing rules in the CAM. Rules can overlap if a query exists that can results in a match to both rules. In the event there is no overlap between a new rule and existing rules, the new CAM entry can be written into a free location within the CAM.
According to one aspect of the embodiments, existing rules that overlap can be arranged into a graph group within the CAM. A graph group can indicate a particular order for the rules within the CAM according to priority. If a new rule overlaps an existing rule within a graph group, a preceding and succeeding rule can be determined according to the priority of the new rule and the priority of the existing rules in the group. If one or more free locations exist between the locations storing the preceding and succeeding rules, the new rule can be written into such a free location.
According to another aspect of the embodiments, if no free locations exist between the locations storing the preceding and succeeding rules, the rules for the entire group can be erased and then rewritten into the CAM as a new group that includes the new rule.
According to another aspect of the embodiments, if a new rule overlaps existing rules within two or more graph groups, the two graph groups can be merged into a single graph group that includes the new rule.
According to another aspect of the embodiments, rules can include a number of bit locations that can have a xe2x80x9c1xe2x80x9d value, xe2x80x9c0xe2x80x9d value, and an xe2x80x9cXxe2x80x9d value, where an X value will match either a 1 or 0 value. Overlaps between a new rule and existing rules can be determined by comparing various bit locations of the new rule with corresponding bit locations of existing rules. If a corresponding bit location stores different values, and one of the values is not an X value, the rules do not overlap. If all corresponding bit locations store the same values, or if corresponding bit locations store different values but one of the different value is an X value, there is an overlap in the rules.
According to another aspect of the embodiments, a minimum weight spanning tree can be constructed from the existing rules in a CAM. The weights of the spanning tree can be a xe2x80x9cternary distance.xe2x80x9d A ternary distance can be the number of bit locations that differ between two rules, where the bit locations do not include an X value. Overlaps between a new rule and existing rules can be determined by comparing rules according to the minimum weight spanning tree.
According to another aspect of the embodiments, as rules are traversed and compared according to minimum weight spanning tree, a bit vector can be maintained that tracks bit location matches between a new rule and the existing rules.